#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#define LENGTH(a) ((sizeof(a)) / (sizeof(a[0])))
static int m_heap[30];      // 数据
static int m_capacity = 30; // 总的容量
static int m_size = 0;      // 实际容量(初始化为0)
/*
 * 返回data在二叉堆中的索引
 *
 * 返回值：
 *     存在 -- 返回data在数组中的索引
 *     不存在 -- -1
 */
int get_index(int data)
{
    int i = 0;

    for (i = 0; i < m_size; i++)
        if (data == m_heap[i])
            return i;
    return -1;
}
/*
 * 最大堆的向下调整算法
 *
 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *
 * 参数说明：
 *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
 *     end   -- 截至范围(一般为数组中最后一个元素的索引)
 */
static void maxheap_filterdown(int start, int end)
{
    int c = start;       // 当前(current)节点的位置
    int l = 2 * c + 1;   // 左(left)孩子的位置
    int tmp = m_heap[c]; // 当前(current)节点的大小

    while (l <= end)
    {
        // "l"是左孩子，"l+1"是右孩子
        if (l < end && m_heap[l] < m_heap[l + 1])
            l++; // 左右两孩子中选择较大者，即m_heap[l+1]
        if (tmp >= m_heap[l])
            break; //调整结束
        else
        {
            m_heap[c] = m_heap[l];
            c = l;
            l = 2 * l + 1;
        }
    }
    m_heap[c] = tmp;
}

/*
 * 删除最大堆中的data
 *
 * 返回值：
 *      0，成功
 *     -1，失败
 */
int maxheap_remove(int data)
{
    int index;
    // 如果"堆"已空，则返回-1
    if (m_size == 0)
        return -1;

    // 获取data在数组中的索引
    index = get_index(data);
    if (index == -1)
        return -1;
    m_heap[index] = m_heap[--m_size];      // 用最后元素填补
    maxheap_filterdown(index, m_size - 1); // 从index位置开始自上向下调整为最大堆
    return 0;
}
/*
 * 最大堆的向上调整算法(从start开始向上直到0，调整堆)
 *
 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *
 * 参数说明：
 *     start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
 */
static void maxheap_filterup(int start)
{
    int c = start;       // 当前节点(current)的位置
    int p = (c - 1) / 2; // 父(parent)结点的位置
    int tmp = m_heap[c]; // 当前节点(current)的大小

    while (c > 0)
    {
        // 父节点大于当前节点
        if (m_heap[p] >= tmp)
            break;
        else
        {   // 父节点小于当前节点，就调换位置，当前节点作为父节点，来源于一个抢位置的概念
            m_heap[c] = m_heap[p];
            c = p;
            p = (p - 1) / 2; // 再把当前节点和上一个父节点在比较大小
        }
    }
    // 找到合适的索引
    m_heap[c] = tmp; //最后把设置值
}
/*
 * 将data插入到二叉堆中
 *
 * 返回值：
 *     0，表示成功
 *    -1，表示失败
 */
int maxheap_insert(int data)
{
    // 如果"堆"已满，则返回
    if (m_size == m_capacity)
        return -1;

    m_heap[m_size] = data;    // 将"数组"插在表尾
    maxheap_filterup(m_size); // 向上调整堆
    m_size++;                 // 堆的实际容量+1

    return 0;
}

void maxheap_print()
{
    int i;
    for (i = 0; i < m_size; i++)
        printf("%d ", m_heap[i]);
}
void main()
{
    int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
    int i, len = LENGTH(a);
    printf("== 堆排序: ");
    for (i = 0; i < len; i++)
    {
        printf("%d \r\n", a[i]);
        maxheap_insert(a[i]);
        printf("round %d result:\r\n");
        for (uint8_t z = 0; z < m_size; z++)
        {
            printf("%d\r\n", m_heap[z]);
        }
        printf("end\r\n");
    }
    printf("\n== 最 大 堆: ");
    maxheap_print();
    i = 85;
    maxheap_insert(i);
    printf("\n== 添加元素: %d", i);
    printf("\n== 最 大 堆: ");
    maxheap_print();
    i = 90;
    maxheap_remove(i);
    printf("\n== 删除元素: %d", i);
    printf("\n== 最 大 堆: ");
    maxheap_print();
    printf("\n");
}






